#include <vector>
#include <algorithm>
using namespace std;
class Solution
{
public:
    int rob(vector<int> &nums)
    {
        // 每个屋子的状态 能偷 不能偷
        // 能偷有两种情况 偷0 不偷1 不能偷2
        // 状态机 状态转移方程:
        //       dp[i][0]=max(dp[i-1][2]+nums[i],dp[i-1][1]+nums[i])
        //       dp[i][1]=max(dp[i-1][1],dp[i-1][2])
        //       dp[i][2]=dp[i-1][0]
        // 初始化 dp[0][0]=nums[0] dp[0][1]=0,dp[0][2]=0
        vector<vector<int>> dp(nums.size(), vector<int>(3, 0));
        dp[0][0] = nums[0], dp[0][1] = 0, dp[0][2] = 0;
        for (int i = 1; i < nums.size(); i++)
        {
            dp[i][0] = max(dp[i - 1][2] + nums[i], dp[i - 1][1] + nums[i]);
            dp[i][1] = max(dp[i - 1][1], dp[i - 1][2]);
            dp[i][2] = dp[i - 1][0];
        }
        return *max_element(dp.back().begin(), dp.back().end());
    }
};